Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,

Given 1->2->3->3->4->4->5, return 1->2->5.

Given 1->1->1->2->3, return 2->3.

Solution:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.   public ListNode deleteDuplicates(ListNode head) {
  11.     if (head == null) {
  12.       return null;
  13.     }
  15.     ListNode fake = new ListNode(0);
  16.     ListNode p = fake;
  17.     ListNode slow = head;
  18.     ListNode fast = head;
  20.     while (fast != null) {
  21.       int count = 0;
  23.       while (fast != null && fast.val == slow.val) {
  24.         count++;
  25.         fast = fast.next;
  26.       }
  28.       if (count == 1) {
  29.         p.next = slow;
  30.         p = p.next;
  31.       }
  33.       slow = fast;
  34.     }
  36.     p.next = null;
  38.     return fake.next;
  39.   }
  40. }